class Trie(object):
    def __init__(self):
        self.__search_map = dict()

    def insert(self, word: str) -> None:
        self.__add(word, self.__search_map)

    def search(self, word: str) -> bool:
        return self.__searchall(word, self.__search_map)

    def startsWith(self, prefix: str) -> bool:
        return self.__searchwith(prefix, self.__search_map)

    def __add(self, s: str, dic: dict):
        if not s:
            dic["end"] = True
            return
        if s[0] not in dic:
            dic[s[0]] = dict()
        self.__add(s[1:], dic[s[0]])

    def __searchall(self, s, dic: dict):
        if not s:
            if "end" in dic:
                return True
            else:
                return False
        if s[0] not in dic:
            return False
        else:
            return self.__searchall(s[1:], dic[s[0]])

    def __searchwith(self, s: str, dic: dict):
        if not s:
            return True
        if s[0] not in dic:
            return False
        else:
            return self.__searchwith(s[1:], dic[s[0]])


class Trie2(object):
    def __init__(self):
        self.search_map = dict()

    def insert(self, word: str) -> None:
        dic = self.search_map
        for s in word:
            if s not in dic:
                dic[s] = dict()
            dic = dic[s]
        dic[1] = 1

    def search(self, word: str) -> bool:
        dic = self.search_map
        for s in word:
            if s not in dic:
                return False
            else:
                dic = dic[s]
        else:
            if 1 in dic:
                return True
            return False

    def startsWith(self, prefix: str) -> bool:
        dic = self.search_map
        for s in prefix:
            if s not in dic:
                return False
            else:
                dic = dic[s]
        return True


a = Trie2()
a.insert("apple")
a.insert("app")
print(a.search_map)
print(a.startsWith("ap"))
print(a.startsWith("t"))
print(a.search("app"))
print(a.search("appl"))
print(a.search("apple"))
